package com.leet.code.lcof;

import com.algorithm.model.TreeNode;
import com.algorithm.model.TreeNodeService;

public class Code26 {

    public static void main(String[] args) {

        TreeNode a = TreeNodeService.getTreeByArray(new int[]{4, 2, 3, 4, 5, 6, 7, 8, 9});
//        TreeNode a = TreeNodeService.getTreeByArray(new int[]{1,0,1,-4,-3});
//        TreeNode a = TreeNodeService.getTreeByArray(new int[]{10, 12, 6, 8, 3, 11});
        TreeNode b = TreeNodeService.getTreeByArray(new int[]{4, 8, 9});
//        TreeNode b = TreeNodeService.getTreeByArray(new int[]{1,-4});
//        TreeNode b = TreeNodeService.getTreeByArray(new int[]{10, 12, 6, 8});

        System.out.println(new Code26().isSubStructure(a, b));
//        System.out.println(new Code26().pp(a, b));


    }


    public boolean isSubStructure(TreeNode A, TreeNode B) {
        if (A == null || B == null) {
            return false;
        }
        return w(A, B);
    }


    public boolean w(TreeNode a, TreeNode b) {
        if (a == null) {
            return false;
        }
        if (pp(a, b)) {
            return true;
        }
        return w(a.left, b) || w(a.right, b);

    }

    public boolean pp(TreeNode a, TreeNode b) {
        if ( b == null) {
            return true;
        }
        if (a == null ) {
            return false;
        }

        if (a.val == b.val) {
            return pp(a.left, b.left) && pp(a.right, b.right);
        }
        return false;
    }


    public boolean p(TreeNode a, TreeNode b) {

        if (b == null) {
            return true;
        }

        if (a == null) {
            return false;
        }

        if (a.val == b.val) {
            return (p(a.left, b.left) && p(a.right, b.right)) || p(a.left, b) || p(a.right, b);
        } else {
            return false;
        }

    }

}
